/*
 * @lc app=leetcode.cn id=211 lang=cpp
 *
 * [211] 添加与搜索单词 - 数据结构设计
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class WordDictionary
{
    struct Node
    {
        bool end;
        Node *next[26];
        Node() : end(false)
        {
            for (int i = 0; i < 26; i++)
            {
                next[i] = nullptr;
            }
        }
    };

    Node *root;

public:
    WordDictionary()
    {
        root = new Node;
    }

    void addWord(string word)
    {
        Node *root = this->root;
        for (int i = 0; i < word.length(); i++)
        {
            const int index = word[i] - 'a';
            if (!(root->next[index]))
            {
                root->next[index] = new Node;
            }

            if (i == word.length() - 1)
                root->next[index]->end = true;

            root = root->next[index];
        }
    }

    bool search(const string &word, int index, Node *root)
    {
        if (nullptr == root)
            return false;

        if (index == word.size())
            return root->end;

        if (word[index] == '.')
        {
            for (int i = 0; i < 26; i++)
            {
                auto n = root->next[i];
                if (n)
                {
                    if (search(word, index + 1, n))
                        return true;
                }
            }
        }
        else
        {
            auto n = root->next[word[index] - 'a'];
            if (n)
            {
                if (search(word, index + 1, n))
                    return true;
            }
        }

        return false;
    }

    bool search(string word)
    {
        return search(word, 0, this->root);
    }
};

// int main(int argc, char const *argv[])
// {
//     WordDictionary w;
//     w.addWord("bad");
//     w.addWord("dad");
//     w.addWord("mad");

//     cout << w.search("pad") << endl;
//     cout << w.search("bad") << endl;
//     cout << w.search(".ad") << endl;
//     cout << w.search("b..") << endl;
//     return 0;
// }

// @lc code=end
